#include <cstdlib>

using namespace std;

// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};

class Solution {
private:
    void dfs(Node* node, Node*& pre) {
        if (node == nullptr) {
            return;
        }
        dfs(node->left, pre);
        pre->right = node;
        node->left = pre;
        pre = node;
        dfs(node->right, pre);
    }
public:
    Node* treeToDoublyList(Node* root) {
        if (root == nullptr) {
            return nullptr;
        }
        Node head(0);
        Node* pre = &head;
        dfs(root, pre);
        head.right->left = pre;
        pre->right = head.right;
        return head.right;
    }
};

int main() {
    Node n1(4), n2(2), n3(5), n4(1), n5(3);
    n1.left = &n2;
    n1.right = &n3;
    n2.left = &n4;
    n2.right = &n5;
    Solution solution;
    solution.treeToDoublyList(&n1);
    return 0;
}